package homework;


import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;


/**
 * @author mubei
 * @date 2021/12/2
 * @description
 */
public class Demo07 {
    static int arr[] = {1, 2, 3, 4, 5, 3, 4, 1, 6, 7, 8, 9, 5, 4, 5, 4, 2, 2, 2};

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);


        exit:
        while (true) {
            print();
            int way = scanner.nextInt();
            switch (way) {
                case 0:
                    System.out.println("结束咯");
                    break exit;
                case 1:
                    System.out.println("输入虚拟内存大小");
                    int size = scanner.nextInt();
                    int count = opt(size, arr);
                    System.out.println("调度了:" + count + "次");
                    break;
                case 2:
                    System.out.println("输入虚拟内存大小");
                    size = scanner.nextInt();
                    count = lru(size);
                    System.out.println("调度了:" + count + "次");
                    break;
                case 3:
                    System.out.println("输入虚拟内存大小");
                    size = scanner.nextInt();
                    count = fifo(size);
                    System.out.println("调度了:" + count + "次");
                    break;
            }
        }

        scanner.close();

    }

    public static void print() {
        System.out.println("输入你要使用的页面置换算法");
        System.out.println("0.退出程序");
        System.out.println("1.opt 最佳页面替换算法 ");
        System.out.println("2.lru 最近未使用算法");
        System.out.println("3.fifo 先进先出");
    }


    public static int fifo(int size){
        Scanner scanner = new Scanner(System.in);
        int countChange = 0;
        System.out.println("输入页面编号数字 #号结束");
        int index = 0;
        FIFO fifo[] = new FIFO[size];
        int arr[] = new int[100];
        int map[][] = new int[size][100];
        char[]  chars= new char[arr.length];
        Arrays.fill(chars, '×');



        for (int i = 0; i < size; i++) {
            fifo[i] = new FIFO();
        }

        while (!scanner.hasNext("#")) {
            int id = scanner.nextInt();
            arr[index] = id;
            int freeBlock = -1;
            int t = -1;


            if(index>0){
                for (int j = 0; j < size; j++) {
                    map[j][index] = map[j][index-1];
                }
            }


            for (int i = 0; i < size; i++) {
               if(fifo[i].firstVisit ==-1 && freeBlock == -1){
                   freeBlock = i;
               } else if(fifo[i].id==id){
                   t = i;
               }
            }
            if(t!=-1){

            }else if(freeBlock != -1){
                fifo[freeBlock] = new FIFO(id,index);
                map[freeBlock][index] = id;
                countChange++;
            }else{
                int minVisited = Integer.MAX_VALUE;
                int p = -1;
                for (int i = 0; i < size; i++) {
                    if(minVisited > fifo[i].firstVisit ){
                        minVisited = fifo[i].firstVisit;
                        p = i;
                    }
                }
                chars[index] = '✓';
                map[p][index] = id;
                fifo[p] = new FIFO(id,index);
                countChange++;
            }
            index ++;
        }

        for (int i = 0; i < index; i++) {
            System.out.print(arr[i]+"\t");
        }
        System.out.println();
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < index; j++) {
                System.out.print(map[i][j]+"\t");
            }
            System.out.println();
        }
        for (int i = 0; i < index; i++) {
            System.out.print((char)chars[i]+"\t");
        }
        System.out.println();
        return countChange;
    }

    public static int lru(int size) {
        Scanner scanner = new Scanner(System.in);
        int countChange = 0;

        System.out.println("输入页面编号数字 #号结束");
        int index = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        while (!scanner.hasNext("#")) {
            int id = scanner.nextInt();
            if (map.containsKey(id)) {//更新最近使用时间
                System.out.println("当前虚拟内存有该页面 " + id + ":更新最近使用");
                map.put(id, index);
                countChange++;
            } else {
                if (map.size() < size) {// 虚拟地址有空余
                    map.put(id, index);
                    System.out.println("当前虚拟内存有空余 将 " + id + ":添加到内存中");
                } else {
                    LRU lru[] = new LRU[size];
                    int t = 0;
                    for (Integer integer : map.keySet()) {
                        lru[t++] = new LRU(integer, map.get(integer));
                    }
                    Arrays.sort(lru);
                    System.out.println("将页面:" + lru[0].id + "替换成" + id);
                    map.remove(lru[0].id);
                    map.put(id, index);
                    countChange++;
                }
            }
            index++;
            if (!map.isEmpty()) {
                printMap(map);
            }
        }

        return countChange;
    }

    public static void printMap(HashMap<Integer, Integer> map) {
        for (Integer integer : map.keySet()) {
            System.out.print(integer + "页面最近在" + map.get(integer) + "使用      ");
        }
        System.out.println();
    }


    public static int opt(int size, int arr[]) {
        System.out.println("opt页面替换算法");
        int countChange = 0;
        OPT[] lrus = new OPT[size];
        int map[][] = new int[size][arr.length];
        char[]  chars= new char[arr.length];
        Arrays.fill(chars, '×');

        int count = 0;
        for (int i = 0; i < arr.length; i++) {

            if(i>0){
                for (int j = 0; j < size; j++) {
                    map[j][i] = map[j][i-1];
                }
            }

            boolean flag = true;
            for (int j = 0; j < count; j++) {
                if (lrus[j].id == arr[i]) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                countChange++;
                if (count == size) {
                    for (OPT lru : lrus) {
                        lru.lastIndex = arr.length;
                    }
                    for (int j = i + 1; j < arr.length; j++) {
                        for (OPT lru : lrus) {
                            if (lru.id == arr[j]) {
                                lru.lastIndex = Math.min(j, lru.lastIndex);
                            }
                        }
                    }
                    Arrays.sort(lrus);
                    int p = -1;
                    for (int j = 0; j < size; j++) {
                        if(map[j][i-1] == lrus[0].id){
                            p =j;
                            break;
                        }
                    }
                    map[p][i] = arr[i];
                    chars[i] = '✓';
                    System.out.println("将页面:" + lrus[0].id + "  置换成页面" + arr[i]);
                    lrus[0] = new OPT(arr[i]);
                } else {
                    map[count][i] = arr[i];
                    System.out.println("将页面:" + arr[i] + "  添加到虚拟内存:" + (count));
                    lrus[count++] = new OPT(arr[i]);
                }
            } else {
                System.out.println("第" + (i + 1) + "个页面:" + arr[i] + "在虚拟内存中存在 不需要替换");
            }
        }

        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+"\t");
        }
        System.out.println();
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < arr.length; j++) {
                System.out.print(map[i][j]+"\t");
            }
            System.out.println();
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print((char)chars[i]+"\t");
        }
        System.out.println();
        return countChange;
    }
}

class FIFO implements Comparable<FIFO>{

    int id;
    int firstVisit;

    public FIFO(int id, int firstVisit) {
        this.id = id;
        this.firstVisit = firstVisit;
    }

    public FIFO() {
        this.id = -1;
        this.firstVisit = -1;
    }

    @Override
    public int compareTo(FIFO o) {
        return 0;
    }
}

class LRU implements Comparable<LRU> {
    int id;
    int lastIndex;

    public LRU(int id, int lastIndex) {
        this.id = id;
        this.lastIndex = lastIndex;
    }


    @Override
    public int compareTo(LRU o) {
        return Integer.compare(this.lastIndex, o.lastIndex);
    }
}

class OPT implements Comparable {
    int id;
    int lastIndex;

    public OPT(int id) {
        this.id = id;
    }

    @Override
    public int compareTo(Object o) {
        OPT l = (OPT) o;
        return Integer.compare(l.lastIndex, this.lastIndex);
    }
}